package T41_T50;
import datastructure.TreeNode;
public class T47 {
    /*思路：
     * 先序遍历第一个节点是二叉树根节点
     * 根据二叉树性质
     * 先序遍历可分为 根节点|左子树|右子树
     * 中序遍历可分为 左子树|根节点|右子树
     * 分治思想
     * */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen=preorder.length;
        int inLen=inorder.length;
        if (preLen!=inLen){
            throw new RuntimeException("两次遍历参数不一致！");
        }
        return buildTree(preorder,0,preLen-1,inorder,0,inLen-1);

    }
    public TreeNode buildTree(int[] preorder,int preL,int preR,
                              int[] inorder,int inL,int inR){
        //递归终止条件:左边界大于右边界
        if (preL>preR||inL>inR)return null;
        //找到根结点在中序遍历数组中的位置
        //pivot存储根结点
        int pivot=preorder[preL];
        TreeNode node= new TreeNode(pivot);
        //pivotIndex为中序遍历数组中根结点位置
        int pivotIndex=inL;
        while(pivot!=inorder[pivotIndex]){
            pivotIndex++;
        }
        node.left=buildTree(preorder,preL+1,preL+pivotIndex-inL,
                inorder,inL,pivotIndex-1);
        node.right=buildTree(preorder,preL+pivotIndex-inL+1,preR,
                inorder,pivotIndex+1,inR);
        return node;
    }
}
